package afi.ch2;

/**
 * @author Pavel Belevich
 *         Date: Jun 28, 2012
 *         Time: 11:20:31 AM
 */
/*
2.4 FINDING THE MIN AND MAX SIMULTANEOUSLY
Given a set of numbers, you can find either the min or max of the set in
N-l comparisons each. When you need to find both, cm you do better
than 2N - 3 comparisons?
Problem 2.4: Find the min and max elements from a set of N elements
using no more than 3N/2 - 1 comparisons.
 */
public class Problem4 {

    static class Pair {

        public int min;
        public int max;
        public int counter;

    }

    /*
    METHOD 1 (Simple Linear Search)
    Initialize values of min and max as minimum and maximum of the first two elements respectively.
    Starting from 3rd, compare each element with max and min, and change max and min accordingly
    (i.e., if the element is smaller than min then change min,
    else if the element is greater than max then change max, else ignore the element)
    total number of comparisons is 1 + 2(n-2) in worst case and 1 + n  2 in best case.
     */
    static Pair getMinMax1(int a[]) {
        if (a.length == 0) {
            return null;
        }
        Pair pair = new Pair();
        if (a.length == 1) {
            pair.min = a[0];
            pair.max = a[0];
            return pair;
        }

        if (a[0] > a[1]) {
            pair.min = a[1];
            pair.max = a[0];
        } else {
            pair.min = a[0];
            pair.max = a[1];
        }
        pair.counter++;
        

        for (int i = 2; i < a.length; i++) {
            if (a[i] > pair.max) {
                pair.max = a[i];
            } else {
                pair.counter++;
                if (a[i] < pair.min) {
                    pair.min = a[i];
                }
            }
            pair.counter++;
        }

        return pair;
    }

    /*
    METHOD 2 (Tournament Method)
    Divide the array into two parts and compare the maximums and minimums of the the two parts
    to get the maximum and the minimum of the the whole array.
    Time Complexity: O(n)
    
    Total number of comparisons: let number of comparisons be T(n). T(n) can be written as follows:
    Algorithmic Paradigm: Divide and Conquer


      T(n) = T(floor(n/2)) + T(ceil(n/2)) + 2
      T(2) = 1
      T(1) = 0

    If n is a power of 2, then we can write T(n) as:

       T(n) = 2T(n/2) + 2

    After solving above recursion, we get

      T(n)  = 3/2n -2

    Thus, the approach does 3/2n -2 comparisons if n is a power of 2. And it does more than 3/2n -2 comparisons if n is not a power of 2.
     */
    static Pair getMinMax2(int a[]) {
        return getMinMax2(a, 0, a.length-1);
    }

    static Pair getMinMax2(int a[], int low, int high) {
        if (a.length == 0) {
            return null;
        }

        /* If there is only on element */
        Pair pair = new Pair();
        if (low == high) {
            pair.min = a[low];
            pair.max = a[low];
            return pair;
        }

        /* If there are two elements */
        if (high == low+1) {
            if (a[low] > a[high]) {
                pair.max = a[low];
                pair.min = a[high];
            } else {
                pair.max = a[high];
                pair.min = a[low];
            }
            pair.counter++;
            return pair;
        }

        /* If there are more than 2 elements */
        int mid = low + (high - low) / 2;
        Pair left = getMinMax2(a, low, mid);
        Pair right = getMinMax2(a, mid, high);
        pair.counter += left.counter;
        pair.counter += right.counter;

        /* compare minimums of two parts*/
        if (left.min < right.min) {
            pair.min = left.min;
        } else {
            pair.min = right.min;
        }
        pair.counter++;

        /* compare maximums of two parts*/
        if (left.max > right.max) {
            pair.max = left.max;
        } else {
            pair.max = right.max;
        }
        pair.counter++;

        return pair;
    }


    public static void main(String[] args) {
        int a[] = {99,4, 2, 6, 12, 8, 1, 3, 5, 8, 10, 32, 53, 20, 100, 200};
        Pair pair1 = getMinMax1(a);
        System.out.println("pair1.min = " + pair1.min);
        System.out.println("pair1.max = " + pair1.max);
        System.out.println("a.length = " + a.length);
        System.out.println("pair1.counter = " + pair1.counter);
        System.out.println("1 + 2(n-2) = " + (1 + 2*(a.length-2)));
        
        Pair pair2 = getMinMax2(a);
        System.out.println("pair2.min = " + pair2.min);
        System.out.println("pair2.max = " + pair2.max);
        System.out.println("a.length = " + a.length);
        System.out.println("pair2.counter = " + pair2.counter);
        System.out.println("3/2n-2 = " + (3.0/2.0*a.length - 2));
    }

}
